1. Field of the Invention
The present invention relates to a page replacement method performed in a system that uses a flash memory as a storage medium, and more particularly, to a page replacement method that can minimize the number of write operations performed on a flash memory and can enhance a memory hit rate.
2. Description of the Related Art
FIG. 1 is a schematic block diagram illustrating a conventional system 100 that uses a flash memory 150 as a storage medium.
Referring to FIG. 1, the system 100 includes a CPU 110, a main memory 120, and the flash memory 150. An operating system 130 is loaded in a portion of the main memory 120. The storage capacity of the main memory 120 is managed by a memory management module 140 included in the operating system 130. In other words, the memory management module 140 manages used pages and free pages of the main memory 120. Here, a page is a unit in which data is written to a memory at one time.
The memory management module 140 allocates a page of the main memory 120 yet to be used for predetermined data stored in the flash memory 150 and reads the predetermined data from the flash memory 150 in order to transfer the predetermined data from the flash memory 150 to the main memory 120.
However, if there are no free pages in the main memory 120, one of the pages of the main memory 120 that have already been used is selected, and the predetermined data read from the flash memory 150 is written to the selected page of the main memory 120. An algorithm that reuses used pages of a memory as new pages is called a page replacement algorithm. Meanwhile, if the selected page of the main memory 120 has already been modified, data stored in the selected page of the main memory 120 is written to the flash memory 150, and the new data is extracted from the flash memory 150. This means that write operations are performed on the flash memory 150.
However, if the selected page of the main memory 120 has not been modified, the flash memory 150 still has an image of the selected page of the main memory 120. Thus, a write operation does not need to be carried out on the flash memory 150, and the selected page of the main memory 120 is removed. Here, the image of the selected page of the main memory 120 is a relative concept. In a case where data stored in an arbitrary page of the main memory 120 is also stored in the flash memory 150, the flash memory 150 is considered having an image of the arbitrary page of the main memory 120. Likewise, in a case where data stored in an arbitrary page of the flash memory 150 is also stored in the main memory 120, the main memory 120 is considered to have an image of the arbitrary page of the flash memory 150.
There are a variety of conventional page replacement algorithms.
Examples of the conventional page replacement algorithms include a first in first out (FIFO) algorithm that replaces a page that has been used first, a least recently used (LRU) algorithm that replaces a page that has been least recently used, a least frequently used (LFU) algorithm that replaces a page that has been least frequently used, and a not recently used (NRU) algorithm that replaces a page that has not been used recently.
FIG. 2 is a diagram illustrating an LRU algorithm that selects a page of the main memory 120 of FIG. 1 that has not been read or written to recently as a page to be replaced. The LRU algorithm is also applicable to a cache memory.
The LRU algorithm is based on the principle of temporal locality, which means that a page that has not been accessed for a long time is not likely to be accessed in the near future.
In the LRU algorithm, a list of a plurality of pages of the main memory 120 is managed so that one of the pages of the main memory 120 that has been most recently accessed tops the corresponding page list.
Referring to FIG. 2, PAGEa (210) is located at the head of a page list because it has been most recently accessed. When Paged (240) is accessed, it is transferred to the head of the page list so that it is followed by page a (210). A page at the tail of the page list, i.e., Pagee (250), is used as a page to be replaced.
FIG. 3 is a diagram illustrating an NRU algorithm.
Referring to FIG. 3, the locations of a plurality of pages, i.e., pages a through e (310 through 350), in a page list, are fixed, and each of pages a through e (310 through 350) has page information represented by 2 bits, i.e., a reference bit 360 and a modified bit 370.
The reference bit 360 is initially set to a value of ‘0’ and is switched to a value of ‘1’ when a corresponding page is used. The modified bit 370 is initially set to a value of ‘0’ and is switched to a value of ‘1’ when the corresponding page is modified. The reference bit 360 is periodically reset to a value of 0 because the corresponding page becomes less likely to be referenced over time.
A pointer 380 points to a page to be replaced. The pointer 380 examines the reference bit 360 and the modified bit 370 of each of pages PAGEa (310), PAGEb (320), PAGEc (330), PAGEd (340), and PAGEe (350) while sequentially moving from PAGEa (310) to PAGEb (320), from PAGEb (320) to PAGEc (330), from PAGEc (330) to PAGEd (340), and from PAGEd (340) to PAGEe (350), and then selects one of PAGEa through PAGEe (310 through 350) as the page to be replaced based on the examination results. When the pointer 380 arrives at the tail of the page list, it moves back to the head of the page list and then performs the above-described operation again.
Here, the pointer 380 selects one of pages a through e (310 through 350) as the page to be replaced according to a set of rules. Specifically, the pointer 380 selects a page, if any, whose reference bit 360 and modified bit 370 are all set to a value of ‘0’ as the page to be replaced. If none of the pages in the page list have the reference bit 360 and the modified bit 370 all set to a value of ‘0’, the pointer 380 selects a page, if any, whose reference bit 360 is set to a value of ‘1’ and whose modified bit 370 is set to a value of ‘0’ as the page to be replaced. If none of the pages in the page list have the reference bit 360 set to a value of ‘1’ and has the modified bit 370 set to a value of ‘0’, the pointer 380 selects a page in the page list whose reference bit 360 and modified bit 370 are all set to a value of ‘1’ as the page to be replaced.
If one of PAGEa through PAGEe (310 through 350) selected as the page to be replaced has already been modified, a write operation is performed on the flash memory 150. However, a delay time required for performing a write operation on the flash memory 150 is generally greater than a delay time required for performing a read operation on the flash memory 150. Thus, the higher the number of write operations performed on the flash memory 150, the greater the delay time.
It is possible to reduce delay time regarding the operation of the flash memory 150 by reducing the number of write operations performed on the flash memory. The LRU algorithm selects a page of the main memory 120 located at the tail of a page list as a page to be replaced regardless of whether the page has been modified. Therefore, when the LRU algorithm is applied to the conventional system 100 of FIG. 1, the performance of the conventional system 100 of FIG. 1 may deteriorate because of frequent write operations performed on the flash memory 150.
In addition, the NRU algorithm does not consider memory hit rate regarding non-modified pages of the main memory 120. Here, the memory hit rate indicates the number of times that the CPU 110 shown in FIG. 1 has successfully obtained meaningful data from the main memory 120 by accessing the main memory 120. In other words, pages of the main memory 120 whose reference bits 360 have the same value and whose modified bits 370 have a value of ‘0’ have the same priority level in terms of page replacement regardless of the memory hit rate.
Therefore, there is a need for development of a page replacement algorithm that minimizes the number of write operations performed on a flash memory while ensuring a memory hit rate.